Volume 1: Fundamental Algorithms, Third Edition

Chapter 1.1: Algorithms

Exercise 1 [10]

The text showed how to interchange the values of variables $m$ and $n$ , using the replacement notation, by setting $t\leftarrow m$ , $m\leftarrow n$ , $n\leftarrow t$ . Show how the values of four variables $(a,b,c,d)$ can be rearranged to $(b,c,d,a)$ by a sequence of replacements. Try to use the minimum number of replacements.

Solution

I am 99% sure that doing the above can be done in at minimum three switches, which I think are fairly obvious.

$a\leftrightarrow b$ to get $(b,a,c,d)$

$c\leftrightarrow a$ to get $(b,c,a,d)$

$a\leftrightarrow d$ to get $(b,c,d,a)$

Corrections

I read the problem wrong, it was asking for $\leftarrow$ replacements instead of replacement $\leftrightarrow$ .

Solution

Basically, put use $t$ as a single placeholder variable and shift everything within around:

$t\leftarrow a$ to get $(a,b,c,d)$ and $t=a$

$a\leftarrow b$ to get $(b,b,c,d)$ and $t=a$

$b\leftarrow c$ to get $(b,c,c,d)$ and $t=a$

$c\leftarrow d$ to get $(b,c,d,d)$ and $t=a$

$d\leftarrow t$ to get $(b,c,d,a)$

Corrections

N/A

Exercise 2 [15]

Prove that $m$ is always greater than $n$ at the beginning of Step E1, except possibly the first time this step occurs

Solution

Either $m>n$ , $m=n$ , or $m<n$ . For each of these situations:

1.

Assume that $m>n$ . In this case, the solution is trivial.
2.

Assume that $m=n$ . We execute Step E1 and get a remainder $r=0$ . At Step E2, the algorithm terminates so we never hit Step E1 again.
3.

Assume that $m<n$ . We execute Step E1 and get the remainder of $r=m$ . We execute Step E3 and set $m\leftarrow n$ and $n\leftarrow r$ . Now, $m$ has the value of the original $n$ and $n$ has the value of the original $m$ . Since $m$ and $n$ have switched, we get the new relationship of $m>n$ .

Corrections

N/A

Exercise 3 [20]

Change Algorithm E (for the sake of efficiency) so that all trivial replacement operations such as “ $m\leftarrow n$ ” are avoided.

Solution

The following algorithm eliminates all trivial replacement operations:

1.

Divide $m$ by $n$ and let $m$ be the remainder
2.

If $m$ is zero, the algorithm terminates; $n$ is the answer
3.

Divide $n$ by $m$ and let $n$ be the remainder
4.

If $n$ is zero, the algorithm terminates; $m$ is the answer
5.

Return to step F1

Corrections

N/A

Exercise 4 [16]

What is the GCD of 2166 and 6099?

Solution

For fun, let’s use the algorithm in Exercise 3 with $m=2166$ and $n=6099$ .

$m$	$n$	$m\%n$	$n\%m$
2166	6099	2166
2166	6099		1767
2166	1767	399
399	1767		171
399	171	57
57	171		0
57	0	0

So the GCD is 57

Corrections

N/A

Exercise 5 [12]

Show that the “Procedure for Reading This Set of Books” that appear after the preface actually fails to be a genuine algorithm on at least three of our five counts. Also mention some differences in format between it an Algorithm E.

Solution

The five counts are as follows:

1.

Finiteness: An algorithm must always terminate after a finite number of steps.
2.

Definiteness: Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
3.

Input: An algorithm has zero or more inputs, quantities that are given to it initially before the algorithm begins, or dynamically as the algorithm runs.
4.

Output: An algorithm has one or more outputs, quantities that have a specified relation to the inputs
5.

Effectiveness: An algorithm is also generally expected to be effective, in the sense that its operations must all be sufficiently basic that they can in principle be done exactly and in a finite length of time by someone using pencil and paper.

The “Procedure for Reading This Set of Books” fails on counts 1, 2, and 4. The procedure is not finite because all 17 steps before the last either point to another step or move on to the next. The final step returns you to step 3, so the procedure will never end. The procedure is not definite because the steps leave some things to the discretion of the reader, which is the opposite of a precise definition. And finally, the procedure has no output, because it never ends.

And here are a few differences with Algorithm E:

•

The procedure lacks a formal end point, where Algorithm E uses a heavy vertical line
•

The procedure is informal and vague, while Algorithm E uses strict notation and language

Corrections

N/A

Exercise 6 [20]

What is $T_{5}$ , the average number of times step E1 is performed when $n=5$ .

Solution

Let’s compute some values for $m\in{1,2,3,4,5}$ . According to the book, to find $T_{n}$ we just do the algorithm for $m=1$ to $m=n$ , count the number of times step E1 has been done, and divide by $n$

•

For $n=5$ and $m=1$ . E1: $1\%5=1$ . E3: $n=1$ and $m=5$ . E1: $5\%1=0$ . End with 2
•

For $n=5$ and $m=2$ . E1: $2\%5=2$ . E3: $n=2$ and $m=5$ . E1: $5\%2=1$ . E3: $n=1$ and $m=2$ . E1: $2\%1=0$ End with 3
•

For $n=5$ and $m=3$ . E1: $3\%5=3$ . E3: $n=3$ and $m=5$ . E1: $5\%3=2$ . E3: $n=2$ and $m=3$ . E1: $3\%2=1$ . E3: $n=1$ and $m=1$ . E1: $1\%1=0$ . End with 4
•

For $n=5$ and $m=4$ . E1: $4\%5=1$ . E3: $n=1$ and $m=5$ . E1: $5\%1=0$ . End with 2
•

For $n=5$ and $m=5$ . E1: $5\%5=0$ . End with 1

The total number of times step E1 has been done is $2+3+4+2+1=12$ and divide by $n=5$ to get 2.4

Corrections

Silly mistake in $m=4$ .

Solution

It should be:

For $n=5$ and $m=4$ . E1: $4\%5=4$ . E3: $n=4$ and $m=5$ . E1: $5\%4=1$ . E3: $n=1$ and $m=4$ . E1: $4\%1=0$ . End with 3

So the total should be $2+3+4+3+1=13$ and divide by $n=5$ to get 2.6

As some additional food for thought, why do we only need to look at values of $m$ up to $n$ ? Let’s say $m=6$ . Then E1: $6\%5=1$ , E3: $n=1$ , $m=5$ . This is identical to $m=1$ , a pattern which will repeat for all values of $m>n$ . Essentially, if $m\%n=x$ , the steps followed are identical for if $m$ had equaled $x$ to start with.

Corrections

N/A

Exercise 7 [HM21]

Let $U_{m}$ be the average number of times that step E1 is executed in Algorithm E, if $m$ is known and $n$ is allowed to range over all positive integers. Show that $U_{m}$ is well defined. Is $U_{m}$ in any way related to $T_{m}$ ?

Solution

Let’s first try some examples I wrote some Python code (TODO: link) to do the computation for values of $n$ from 1 to 1,000,000 with the following results:

$m$	$U_{m}$	Approximation	Expanded Numerator
1	1.999999	2	2
2	2.499997	$2\frac{1}{2}=2.5$	5
3	2.999995	3	9
4	2.999993	3	12
5	3.599991	$3\frac{3}{5}=3.6$	18
6	3.166656	$3\frac{1}{6}\approx 3.1\overline{6}$	19
7	3.857129	$3\frac{6}{7}\approx 3.85714\dots$	27
8	3.749985	$3\frac{6}{8}=3.75$	30
9	3.77776	$3\frac{7}{9}\approx 3.\overline{7}$	34
10	3.699981	$3\frac{3}{10}=3.7$	33
11	4.454523	$4\frac{5}{11}\approx 4.\overline{45}$	49
12	3.666641	$3\frac{8}{12}\approx 3.\overline{6}$	44
13	4.461512	$4\frac{6}{13}\approx 4.46153\dots$	58
14	4.21425	$4\frac{3}{14}\approx 4.21428\dots$	59
15	4.066637	$4\frac{1}{15}\approx 4.0\overline{6}$	61
16	4.124969	$4\frac{2}{16}=4.125$	66
17	4.705847	$4\frac{12}{17}\approx 4.70588\dots$	80
18	4.27774	$4\frac{5}{18}=4.2\overline{7}$	77
19	4.894699	$4\frac{17}{19}\approx 4.8947\dots$	93
20	4.199961	$4\frac{4}{20}=4.2$	84

Note, based on observation of $U_{m}$ as the maximum value of $n$ increases, I am very confident that the value of $U_{m}$ will always converge. Additionally, the problem statement implies that $U_{m}$ is well defined.

Corrections

TODO

Exercise 8 [M25]

Give an “effective” formal algorithm for computing the GCD of positive integers $m$ and $n$ by specifying $\theta_{j},\phi_{j},a_{j},b_{j}$ as in Eqs. (3). Let the input be represented by the string $a^{m}b^{n}$ , that is, $m$ $a$ ’s followed by $n$ $b$ ’s. Try to make your solution as simple as possible. [Hint: Use Algorithm E, but instead of division in step E1, set $r\leftarrow|m-n|$ , $n\leftarrow\text{min}(m,n)$ .]

Solution

TODO

Corrections

TODO

Exercise 9 [M30]

Suppose that $C_{1}=(Q_{1},I_{1},\Omega_{1},f_{1})$ and $C_{2}=(Q_{2},I_{2},\Omega_{2},f_{2})$ are computational methods. For example $C_{1}$ might stand for Algorithm E as in Eqs. (2), except that $m$ and $n$ are restricted in magnitude, and $C_{2}$ might stand for a computer program implementation of Algorithm E. (Thus $Q_{2}$ might be the set of all states of the machine, i.e., all possible configurations of its memory and registers; $f_{2}$ might be the definition of single machine actions; and $I_{2}$ might be the set of initial states, each including the program that determines the GCD as well as the particular values of $m$ and $n$ .)

Formulate a set-theoretic definition for the concept “ $C_{2}$ is a representation of $C_{1}$ ” or “ $C_{2}$ simulates $C_{1}$ ”. This is to mean intuitively that any computation sequence of $C_{1}$ is mimicked by $C_{2}$ , except that $C_{2}$ might take more steps in which to do the computation and it might retain more information in its states

Solution

TODO

Corrections

TODO